package h0907.sort;

import java.util.Arrays;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 快速排序
 * @date 2024/9/7 19:20
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {1,1,2,3,4};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = partition(nums, left, right);
            quickSort(nums, left, mid - 1);
            quickSort(nums, mid + 1, right);
        }
    }

    private static int partition(int[] nums, int left, int right) {
        int start = left + 1;
        int end = right;
        int pivot = nums[left]; //选取基准元素
        while (true) {
            while (start <= end && nums[start] <= pivot) {
                start++;
            }
            while (end >= start && nums[end] > pivot) {
                end--;
            }
            if (start >= end) {
                break;
            }
            swap(nums, start, end);
        }
        swap(nums, end, left);
        return end;
    }

    private static void swap(int[] nums, int start, int end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
}
